package main

import (
	"fmt"
	"sort"
)

func main() {
	arr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8}
	fmt.Printf("src arr = %v\n", arr)

	sortByBits(arr)
	fmt.Printf("dst arr = %v\n", arr)
}

func sortByBits(arr []int) []int {
	oneCount := map[int]int{}
	for _, n := range arr {
		if _, has := oneCount[n]; !has {
			oneCount[n] = getCount(n)
		}
	}

	sort.Slice(arr, func(i, j int) bool {
		if oneCount[arr[i]] == oneCount[arr[j]] {
			return arr[i] < arr[j]
		}
		return oneCount[arr[i]] < oneCount[arr[j]]
	})

	return arr
}

func getCount(n int) int {
	count := 0
	for ; n != 0; count++ {
		n &= (n - 1)
	}
	return count
}
